package binarytree

// 递归
func isBalanced(root *TreeNode) bool {
	if helper110(root) == -1 {
		return false
	}
	return true
}

func helper110(root *TreeNode) int {

	if root == nil {
		return 0
	}

	depthRight := helper110(root.Right)
	depethLeft := helper110(root.Left)
	if abs(depethLeft-depthRight) > 1 {
		return -1
	}
	return max(depethLeft, depthRight) + 1
}

func abs(x int) int {
	if x < 0 {
		return -x
	} else {
		return x
	}
}

func getDepth(root *TreeNode) int {

	if root == nil {
		return 0
	}

	stack := []*TreeNode{root}
	res := 0
	depth := 0
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		if node != nil {
			stack = stack[:len(stack)-1]
			stack = append(stack, node)
			stack = append(stack, nil)
			depth++
			if node.Right != nil {
				stack = append(stack, node.Right)
			}
			if node.Left != nil {
				stack = append(stack, node.Left)
			}
		} else {
			stack = stack[:len(stack)-1]
			if len(stack) > 0 {
				stack = stack[:len(stack)-1]
			}
			depth--
		}
		if depth > res {
			res = depth
		}
	}
	return res

}

func IsBalanced2(root *TreeNode) bool {
	if root == nil {
		return true
	}
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if abs(getDepth(node.Left)-getDepth(node.Right)) > 1 {
			return false
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}

	return true
}
